{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Partition Array into Disjoint Intervals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: partitionDisjoint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个数组&nbsp;<code>nums</code>&nbsp;，将其划分为两个连续子数组&nbsp;<code>left</code>&nbsp;和&nbsp;<code>right</code>，&nbsp;使得：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>left</code>&nbsp;中的每个元素都小于或等于&nbsp;<code>right</code>&nbsp;中的每个元素。</li>\n",
    "\t<li><code>left</code> 和&nbsp;<code>right</code>&nbsp;都是非空的。</li>\n",
    "\t<li><code>left</code> 的长度要尽可能小。</li>\n",
    "</ul>\n",
    "\n",
    "<p><em>在完成这样的分组后返回&nbsp;<code>left</code>&nbsp;的&nbsp;<strong>长度&nbsp;</strong></em>。</p>\n",
    "\n",
    "<p>用例可以保证存在这样的划分方法。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,0,3,8,6]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>left = [5,0,3]，right = [8,6]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1,0,6,12]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>left = [1,1,1,0]，right = [6,12]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li>可以保证至少有一种方法能够按题目所描述的那样对 <code>nums</code> 进行划分。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [partition-array-into-disjoint-intervals](https://leetcode.cn/problems/partition-array-into-disjoint-intervals/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [partition-array-into-disjoint-intervals](https://leetcode.cn/problems/partition-array-into-disjoint-intervals/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,0,3,8,6]', '[1,1,1,0,6,12]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cur_max = left_max = nums[0]\n",
    "        left_pos = 0\n",
    "        for i in range(1, n - 1):\n",
    "            if nums[i] > cur_max:\n",
    "                cur_max = nums[i]\n",
    "            if nums[i] < left_max:\n",
    "                left_max, left_pos = cur_max, i\n",
    "        return left_pos + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        left = 1\n",
    "        leftMax = nums[0]\n",
    "        curMax = nums[0]\n",
    "        for i, x in enumerate(nums):\n",
    "            if x < leftMax:\n",
    "                left = i+1\n",
    "                leftMax = curMax\n",
    "            curMax = max(curMax, x)\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        post_min = [0] * len(nums)\n",
    "        post_min[-1] = nums[-1]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            post_min[i] = min(post_min[i + 1], nums[i])\n",
    "\n",
    "        pre_max = 0\n",
    "        for i in range(0, len(nums) - 1):\n",
    "            pre_max = max(pre_max, nums[i])\n",
    "            if pre_max <= post_min[i + 1]:\n",
    "                return i + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        left = 1\n",
    "        leftMax = nums[0]\n",
    "        curMax = nums[0]\n",
    "        for i, x in enumerate(nums):\n",
    "            if x < leftMax:\n",
    "                left = i+1\n",
    "                leftMax = curMax\n",
    "            curMax = max(curMax, x)\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        leftmax = nums[0]\n",
    "        leftnums = [nums[0]]\n",
    "        start = 1\n",
    "        while True:\n",
    "            a = min(nums[start:])\n",
    "            if leftmax > a:  # 如果左边的最大值大于右边的最小值\n",
    "                start = nums[start:].index(a)+start+1\n",
    "                leftnums = nums[:start]\n",
    "                leftmax = max(leftnums)\n",
    "            else:\n",
    "                return len(leftnums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        max_i = [-1] * (n+2)\n",
    "        min_i = [10000001] * (n+2)\n",
    "        for i in range(n):\n",
    "            max_i[i] = max(max_i[i-1], nums[i])\n",
    "        for i in range(n-1, -1, -1):\n",
    "            min_i[i] = min(min_i[i+1], nums[i])\n",
    "        res = 0\n",
    "        for i in range(n-1):\n",
    "            if max_i[i] <= min_i[i+1]:\n",
    "                res = i+1\n",
    "                break\n",
    "        # print(max_i, min_i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right_min = [0 for _ in range(n)]\n",
    "        right_min[-1] = nums[-1]\n",
    "\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            right_min[i] = min(right_min[i + 1], nums[i])\n",
    "\n",
    "        \n",
    "        # print(right_min)\n",
    "        left_max = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if left_max <= right_min[i]:\n",
    "                return i\n",
    "\n",
    "            if nums[i] > left_max:\n",
    "               left_max = nums[i]\n",
    "            # print(i, left_max, right_min[i])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        r_min = [0] * (n - 1) + [nums[-1]]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            r_min[i] = min(r_min[i + 1], nums[i])\n",
    "        pre_max = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if pre_max <= r_min[i]:\n",
    "                return i\n",
    "            pre_max = max(pre_max, nums[i])\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        maxs, mins = [-1] * n, [inf] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            maxs[i] = max(maxs[i - 1], num)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            mins[i] = min(mins[i + 1] if i < n -1 else inf, nums[i])\n",
    "        for i in range(1, n):\n",
    "            if maxs[i - 1] <= mins[i]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right_min = [0 for _ in range(n)]\n",
    "        right_min[-1] = nums[-1]\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] < right_min[i + 1]:\n",
    "                right_min[i] = nums[i]\n",
    "            else:\n",
    "                right_min[i] = right_min[i + 1]\n",
    "        \n",
    "        left_max = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if left_max <= right_min[i]:\n",
    "                return i\n",
    "\n",
    "            if nums[i] > left_max:\n",
    "               left_max = nums[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\r\n",
    "        right=[inf]*(len(nums)+1)\r\n",
    "        for i in range(len(nums)-1,-1,-1):\r\n",
    "            right[i]=min(right[i+1],nums[i])\r\n",
    "        ma=0\r\n",
    "        print(right)\r\n",
    "        for i in range(len(nums)):\r\n",
    "            ma=max(ma,nums[i])\r\n",
    "            if ma<=right[i+1]:\r\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        left_b = [0 for _ in range(len(nums))]\n",
    "        left_b[0] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            left_b[i] = max(left_b[i - 1], nums[i])\n",
    "            pass\n",
    "        right_s = [0 for _ in range(len(nums))]\n",
    "        right_s[len(nums) - 1 - 1] = nums[len(nums) - 1]\n",
    "        p = len(nums) - 1 - 1 - 1\n",
    "        while p >= 0:\n",
    "            right_s[p] = min(right_s[p + 1], nums[p + 1])\n",
    "            p -= 1\n",
    "            pass\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if left_b[i] <= right_s[i] :\n",
    "                return i + 1\n",
    "            pass\n",
    "\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def partitionDisjoint(self, nums: list[int]) -> int:\r\n",
    "        max_arr = []\r\n",
    "        min_arr = []\r\n",
    "        for i in range(len(nums) - 1):\r\n",
    "            if i == 0:\r\n",
    "                max_arr.append(nums[i])\r\n",
    "            else:\r\n",
    "                max_arr.append(max(max_arr[-1], nums[i]))\r\n",
    "        for i in range(len(nums) - 1, 0, -1):\r\n",
    "            if i == len(nums) - 1:\r\n",
    "                min_arr.append(nums[i])\r\n",
    "            else:\r\n",
    "                min_arr.append(min(min_arr[-1], nums[i]))\r\n",
    "        min_arr.reverse()\r\n",
    "        for i in range(len(nums)):\r\n",
    "            if max_arr[i] <= min_arr[i]:\r\n",
    "                return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        left_max, right_min = [nums[0]], [nums[-1]]\n",
    "        for i in range(1, len(nums)):\n",
    "            left_max.append(max(left_max[-1], nums[i]))\n",
    "            right_min.append(min(right_min[-1], nums[len(nums) - i - 1]))\n",
    "        for i in range(len(nums)):\n",
    "            if left_max[i] <= right_min[len(nums) - i - 2]:\n",
    "                return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        M = len(nums)\n",
    "        left = [nums[0]] + [0] * (M - 1)\n",
    "        for i in range(1, M):\n",
    "            left[i] = max(left[i - 1], nums[i])\n",
    "        right = [0] * (M - 1) + [nums[-1]]\n",
    "        for i in range(M - 2, -1, -1):\n",
    "            right[i] = min(right[i + 1], nums[i])\n",
    "        for i in range(M):\n",
    "            if left[i] <= right[i + 1]:\n",
    "                return i + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = [nums[0]] + [0] * (n - 1)\n",
    "        right = [inf] * (n - 1) + [nums[-1]]\n",
    "        for i in range(1, n):\n",
    "            left[i] = max(left[i - 1], nums[i])\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            right[j] = min(right[j + 1], nums[j])\n",
    "        for k in range(n - 1):\n",
    "            if left[k] <= right[k + 1]:\n",
    "                return k + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        idx = sorted(range(len(nums)), key=lambda x : nums[x])\n",
    "        max_v = 0\n",
    "        for i in range(len(idx)):\n",
    "            max_v = max(max_v, idx[i])\n",
    "            if i == max_v:\n",
    "                return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        prefixMax = []\n",
    "        m = 0\n",
    "        for v in nums:\n",
    "            m = max(v, m)\n",
    "            prefixMax.append(m)\n",
    "\n",
    "        \n",
    "        suffixMin = []\n",
    "        m = 10_000_000\n",
    "        for v in reversed(nums):\n",
    "            m = min(m, v)\n",
    "            suffixMin.append(m)\n",
    "\n",
    "        suffixMin = list(reversed(suffixMin))\n",
    "        print(prefixMax)\n",
    "        print(suffixMin)\n",
    "\n",
    "        for i, (M, m) in enumerate(zip(prefixMax[:-1], suffixMin[1:])):\n",
    "            if M <= m:\n",
    "                return i + 1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        # 存储包括此数值以后的最小值\n",
    "        min_values = [ None for _ in range(len(nums))]\n",
    "        max_values = [ None for _ in range(len(nums))]\n",
    "        min_value = nums[-1]\n",
    "        max_value = nums[0]\n",
    "        for i in range(-2,-len(nums)-1,-1):\n",
    "            min_value = min(nums[i+1], min_value)\n",
    "            min_values[i] = min_value\n",
    "\n",
    "        for i in range(0,len(nums),1):\n",
    "            max_value = max(nums[i], max_value)\n",
    "            max_values[i] = max_value\n",
    "\n",
    "        print(max_values, min_values)\n",
    "\n",
    "        for i, maxv, minv in zip(range(len(nums)), max_values, min_values):\n",
    "            print(i, maxv, minv)\n",
    "            if maxv <= minv:\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        a = Counter(nums)\n",
    "        seen = set()\n",
    "        r = []\n",
    "        for i in a:\n",
    "            r.append(i)\n",
    "        r.sort()    \n",
    "        max_val = nums[0]\n",
    "        min_val = r[0]\n",
    "        i = 0\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        while max_val > min_val:\n",
    "            max_val = max(max_val,nums[j])\n",
    "            a[nums[j]] -= 1\n",
    "            j += 1\n",
    "            while a[min_val] == 0:\n",
    "                i += 1\n",
    "                min_val = r[i]\n",
    "            ans += 1\n",
    "        return 1 if ans == 0 else ans   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        count = defaultdict(int)\n",
    "        for i in nums:\n",
    "            count[i]+=1\n",
    "        nums_sort = sorted(nums,reverse=True)\n",
    "        max_l = 0\n",
    "        min_r = nums_sort.pop()\n",
    "        for i in range(len(nums)-1):\n",
    "            count[nums[i]]-=1\n",
    "            max_l = max([max_l,nums[i]])\n",
    "            if min_r == nums[i]:\n",
    "                while count[min_r] == 0:\n",
    "                    min_r = nums_sort.pop()\n",
    "            if max_l <= min_r:\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l_max = [nums[0]]\n",
    "        r_min = [nums[-1]]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            l_max.append(max(l_max[-1], nums[i]))\n",
    "            r_min.append(min(r_min[-1], nums[n-1-i]))\n",
    "        print(l_max)\n",
    "        print(r_min)\n",
    "\n",
    "        for k in range(n):\n",
    "            if l_max[k] <= r_min[n-2-k]:\n",
    "                return k + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l_max = [nums[0]]\n",
    "        r_min = [nums[-1]]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            l_max.append(max(l_max[-1], nums[i]))\n",
    "            r_min.append(min(r_min[-1], nums[n-1-i]))\n",
    "        print(l_max)\n",
    "        print(r_min)\n",
    "\n",
    "        for k in range(n):\n",
    "            if l_max[k] <= r_min[n-2-k]:\n",
    "                return k + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        ma = list(itertools.accumulate(nums, max))\n",
    "        mi = list(itertools.accumulate(nums[::-1], min))[::-1]\n",
    "        for idx, (a, i) in enumerate(zip([float('+inf')] + ma, mi + [float('-inf')])):\n",
    "            if a <= i:\n",
    "                return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        max_l=nums[0]\n",
    "        c = Counter(nums[1:])\n",
    "        l = sorted(c.keys(), reverse=True)\n",
    "        for i in range(1, len(nums)):\n",
    "            if l[-1]>=max_l: return i\n",
    "            c[nums[i]] -= 1\n",
    "            max_l = max(max_l, nums[i])\n",
    "            while c[l[-1]]==0: l.pop()\n",
    "        return len(i)-1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        min_arr = [nums[-1] for i in range(l)]\n",
    "        min_num = nums[-1]\n",
    "        max_num = nums[0]\n",
    "        max_arr = [nums[0] for i in range(l)]\n",
    "        for i, n in enumerate(nums[::-1]):\n",
    "            min_num = min(min_num, n)\n",
    "            min_arr[l-1-i] = min_num\n",
    "        \n",
    "        for i, n in enumerate(nums):\n",
    "            max_num = max(max_num, n)\n",
    "            max_arr[i] = max_num\n",
    "        \n",
    "        print(min_arr)\n",
    "        print(max_arr)\n",
    "\n",
    "        for i in range(l-1):\n",
    "            if max_arr[i] <= min_arr[i+1]:\n",
    "                return i+1\n",
    "        return 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        minn = [1000000000]*len(nums)\n",
    "        minn[-1] = nums[-1]\n",
    "        maxx = [-1]*len(nums)\n",
    "        maxx[0] = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            maxx[i] = max(maxx[i-1],nums[i])\n",
    "            minn[len(nums)-1-i] = min(minn[len(nums)-1-i+1],nums[len(nums)-1-i])\n",
    "        print(maxx)\n",
    "        print(minn)\n",
    "        for i in range(1,len(nums)):\n",
    "            if maxx[i-1]<=minn[i]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        pre_max = [0] * len(nums)\n",
    "        pre_max[0] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            pre_max[i] = max(pre_max[i - 1], nums[i])\n",
    "\n",
    "        post_min = [0] * len(nums)\n",
    "        post_min[-1] = nums[-1]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            post_min[i] = min(post_min[i + 1], nums[i])\n",
    "\n",
    "        print(pre_max, post_min)\n",
    "\n",
    "        for i in range(len(nums) - 1):\n",
    "            if pre_max[i] <= post_min[i + 1]:\n",
    "                return i+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums_sort=sorted(nums)\n",
    "        ref={}\n",
    "        for i,x in enumerate(nums_sort,1):\n",
    "            if x not in ref:\n",
    "                ref[x]=i\n",
    "\n",
    "        c=0\n",
    "        cnt=0\n",
    "        for i,x in enumerate(nums,1):\n",
    "            if ref[x]>c:\n",
    "                c=ref[x]\n",
    "                cnt=0\n",
    "            elif ref[x]==c:\n",
    "                cnt+=1\n",
    "            if c+cnt==i:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        leftMax, rightMin = float(\"-inf\"), float(\"inf\")\n",
    "        n = len(nums)\n",
    "        tmp = [[None] * 2 for _ in range(n - 1)]\n",
    "\n",
    "        for l in range(1, n):\n",
    "            leftMax = max(leftMax, nums[l - 1])\n",
    "            rightMin = min(rightMin, nums[n - l])\n",
    "            tmp[l - 1][0] = leftMax\n",
    "            tmp[n - 1 - l][1] = rightMin\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if tmp[i][0] <= tmp[i][1]:\n",
    "                return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        # 懒删除堆  哈希表 + 队就性\n",
    "        mx = 0\n",
    "        n = len(nums)\n",
    "        m = Counter(nums)\n",
    "        h = nums.copy()\n",
    "        heapify(h)\n",
    "\n",
    "        for i in range(n-1):\n",
    "            mx = max(mx, nums[i])\n",
    "            m[nums[i]] -= 1\n",
    "            while m[h[0]] == 0:\n",
    "                heappop(h)\n",
    "            if h[0] >= mx:\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "       q,e=[nums[-1]],[nums[0]]\n",
    "       pr=nums[0]\n",
    "       for x in nums[1:]:\n",
    "           if x>pr:\n",
    "             e.append(x)\n",
    "           else:\n",
    "             e.append(pr)\n",
    "           pr=max(pr,x)\n",
    "       pr=nums[-1]    \n",
    "       for x in nums[1:-1][::-1]:\n",
    "           if x>pr:\n",
    "             q.append(pr)\n",
    "           else:\n",
    "             q.append(x)\n",
    "           pr=min(pr,x)\n",
    "       q=q[::-1] \n",
    "       print(q,e)\n",
    "       i=0\n",
    "       for x,y in zip(q,e):\n",
    "         if x>=y:\n",
    "           return i+1\n",
    "         i+=1    \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        record = [[nums[0], nums[-1]] for each in range(n)]\n",
    "        for i in range(1, n):\n",
    "            record[i][0] = max(record[i-1][0], nums[i])\n",
    "            record[n - i - 1][1] = min(record[n - i][1], nums[n - i - 1])\n",
    "        for i in range(len(record)):\n",
    "            if record[i][0] <= record[i + 1][1]:\n",
    "                return i + 1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        ma_left = nums[0]\n",
    "        d = collections.Counter(nums[ans:])\n",
    "        lis = list(set(nums[1:]))\n",
    "        lis.sort()\n",
    "        lis = lis[::-1]\n",
    "        mi_right = lis[-1]\n",
    "        for i in range(len(nums)-1):\n",
    "            if ma_left <= mi_right:\n",
    "                return ans\n",
    "            d[nums[ans]] -= 1\n",
    "            \n",
    "            while not d[mi_right]:\n",
    "                lis.pop()\n",
    "                mi_right = lis[-1]\n",
    "\n",
    "            ma_left = max(ma_left,nums[ans])\n",
    "            ans += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        ll = len(nums)\n",
    "        tleft = nums[0]\n",
    "        for i, x in enumerate(nums):\n",
    "            dic[x] = i\n",
    "        dic = sorted(dic.items(), reverse=True)\n",
    "        t = dic[-1][1]\n",
    "        # print(dic)\n",
    "        i = 0\n",
    "        while tleft > dic[-1][0]:\n",
    "            for i in range(i, t+1):\n",
    "                # print(i)\n",
    "                tleft = max(tleft, nums[i])\n",
    "            i += 1\n",
    "            while dic[-1][1] < i:\n",
    "                dic.pop()\n",
    "            t = dic[-1][1]\n",
    "            # print(i)\n",
    "            # print(dic)\n",
    "            # break\n",
    "        return max(1, i)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        t = sorted((j,i) for i,j in enumerate(nums))\n",
    "        a = 0\n",
    "        m = 0\n",
    "        for i ,j in t:\n",
    "            a = max(a,j)\n",
    "            if m == a:\n",
    "                return m + 1\n",
    "            m += 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        a = {}\n",
    "        for num in nums:\n",
    "            if num in a:\n",
    "                a[num] += 1\n",
    "            else:\n",
    "                a[num] = 1\n",
    "        n = len(nums)\n",
    "        maxl = 0\n",
    "        minr = min(nums)\n",
    "        for i in range(n):\n",
    "            maxl = max(maxl,nums[i])\n",
    "            a[nums[i]] -= 1\n",
    "            if a[nums[i]] == 0:\n",
    "                a.pop(nums[i])\n",
    "            if nums[i] == minr:\n",
    "                minr = min(a.keys())\n",
    "            if maxl <= minr:\n",
    "                return i+1\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "\n",
    "        self.tree = [None] * (n * 4 + 1)\n",
    "\n",
    "        def build_tree(tree_index, left, right):\n",
    "            if left == right:\n",
    "                self.tree[tree_index] = (A[left], A[left])\n",
    "                return self.tree[tree_index]\n",
    "            else:\n",
    "                mid = left + (right - left) // 2\n",
    "                left_c_id = tree_index * 2\n",
    "                right_c_id = left_c_id + 1\n",
    "                lm = build_tree(left_c_id, left, mid)\n",
    "                rm = build_tree(right_c_id, mid + 1, right)\n",
    "                self.tree[tree_index] = min(lm[0], rm[0]), max(lm[1], rm[1])\n",
    "                return self.tree[tree_index] \n",
    "        \n",
    "        def search(tree_index, l, r, ql, qr):\n",
    "            if l == ql and r == qr:\n",
    "                return self.tree[tree_index]\n",
    "            \n",
    "            mid = l + (r - l) // 2\n",
    "            left_c_id = tree_index * 2\n",
    "            right_c_id = left_c_id + 1\n",
    "\n",
    "            if qr <= mid:\n",
    "                return search(left_c_id, l, mid, ql, qr)\n",
    "            elif ql > mid:\n",
    "                return search(right_c_id, mid + 1, r, ql, qr)\n",
    "            else:\n",
    "                lm = search(left_c_id, l, mid, ql, mid)\n",
    "                rm = search(right_c_id, mid + 1, r, mid + 1, qr)\n",
    "                return min(lm[0], rm[0]), max(lm[1], rm[1])\n",
    "\n",
    "        build_tree(1, 0, n - 1)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            left_max = search(1, 0, n - 1, 0, i - 1)[1]\n",
    "            right_min = search(1, 0, n - 1, i, n - 1)[0]\n",
    "            # print(left_max, right_min)\n",
    "            if left_max <= right_min:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        # 剩余right的最小值要>= 左边的最大值\n",
    "        # 优先队列得到左边最大\n",
    "        # 小根堆得到右边最小\n",
    "        pq = []\n",
    "        heap = [(num,i) for i,num in enumerate(nums)]\n",
    "        heapify(heap)\n",
    "        for i,num in enumerate(nums):\n",
    "            while pq and num >= pq[-1]:\n",
    "                pq.pop()\n",
    "            pq.append(num)\n",
    "            while heap and heap[0][1] <= i:\n",
    "                heappop(heap)\n",
    "            if heap[0][0] >= pq[0]:\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        enum = list(enumerate(nums))\n",
    "        enum.sort(key=lambda a: a[1])\n",
    "        cnt = 0\n",
    "        max_idx = 0\n",
    "        for i in enum:\n",
    "            cnt += 1\n",
    "            max_idx = max(max_idx, i[0])\n",
    "            if cnt == max_idx+1:\n",
    "                return cnt\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        # 剩余right的最小值要>= 左边的最大值\n",
    "        # 优先队列得到左边最大\n",
    "        # 小根堆得到右边最小\n",
    "        pq = []\n",
    "        heap = [(num,i) for i,num in enumerate(nums)]\n",
    "        heapify(heap)\n",
    "        for i,num in enumerate(nums):\n",
    "            while pq and num >= pq[-1]:\n",
    "                pq.pop()\n",
    "            pq.append(num)\n",
    "            while heap and heap[0][1] <= i:\n",
    "                heappop(heap)\n",
    "            if heap[0][0] >= pq[0]:\n",
    "                return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # mi = nums[-1]\n",
    "        # mii = n-1\n",
    "        # for i in range(len(nums)-1,0,-1):\n",
    "        #     if nums[0]>nums[i]:\n",
    "        #         break\n",
    "        #     if nums[i]<mi:\n",
    "        #         mi = nums[i]\n",
    "        #         mii = i\n",
    "        # else:\n",
    "        #     return 1\n",
    "        # ma = max(nums[:i+1])\n",
    "        # if ma<=mi: return i+1\n",
    "        # else:\n",
    "        #     ma = max(ma,max(nums[i+1:mii+1]))\n",
    "        lst = sorted((j,i) for i,j in enumerate(nums))\n",
    "        i = bisect_left(lst,nums[0],key=lambda x:x[0])\n",
    "        if i==0: return 1\n",
    "        m = max(lst[j][1] for j in range(i))\n",
    "        _m = m\n",
    "        for j in range(i+1,n):\n",
    "            if lst[j][1]<m:\n",
    "                m = _m\n",
    "            _m = max(_m,lst[j][1])\n",
    "        return m+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n, minv, maxv = len(nums), 1000010, -1\n",
    "        p = [[0 for i in range(2)] for j in range(n)]\n",
    "        for i in range(n):\n",
    "            maxv = max(maxv, nums[i])\n",
    "            minv = min(minv, nums[n - i - 1])\n",
    "            p[i][0] = maxv\n",
    "            p[n - i - 1][1] = minv\n",
    "        for i in range(n - 1):\n",
    "            if p[i][0] <= p[i + 1][1]:\n",
    "                return i + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        left_max = -1\n",
    "        remain = [(nums[i], i) for i in range(len(nums))]\n",
    "        heapq.heapify(remain)\n",
    "        for i in range(len(nums) - 1):\n",
    "            left_max = max(left_max, nums[i])\n",
    "            while remain[0][1] <= i:\n",
    "                heapq.heappop(remain)\n",
    "            if left_max <= remain[0][0]:\n",
    "                return i + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        heap, cur_max = [(v, i) for i, v in enumerate(nums)], nums[0]\n",
    "        heapq.heapify(heap)\n",
    "        for i, v in enumerate(nums):\n",
    "            if v > cur_max:\n",
    "                cur_max = v\n",
    "            while heap[0][1] <= i:\n",
    "                heapq.heappop(heap)\n",
    "            if cur_max <= heap[0][0]:\n",
    "                return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        # [5,0,3,8,6]\n",
    "        # [2,0,1,4,3]\n",
    "        # [1,1,1,0,6,12]\n",
    "        # [1,2,3,0,4,5]\n",
    "        n = len(nums)\n",
    "        sortNums = sorted(zip(nums, list(range(n))), key=lambda x: x[0])\n",
    "        sortIdx = [pair[1] for pair in sortNums]\n",
    "        minIdx = 0\n",
    "        for i, num in enumerate(sortIdx):\n",
    "            minIdx = max(minIdx, num)\n",
    "            if i == minIdx:\n",
    "                break\n",
    "        return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        left = nums[0]\n",
    "        right = nums[-1]\n",
    "        max = [0]*len(nums)\n",
    "        min = [0]*len(nums)\n",
    "        for i,num in enumerate(nums):\n",
    "            if num > left:\n",
    "                left = num\n",
    "            max[i] = left\n",
    "        for i,num in reversed(list(enumerate(nums))):\n",
    "            if num < right:\n",
    "                right = num\n",
    "            min[i] = right\n",
    "        for i in range(0,len(nums)-1):\n",
    "            if max[i]<=min[i+1]:\n",
    "                return i+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, s: List[int]) -> int:\n",
    "        t = [(v, i) for i, v in enumerate(s)]\n",
    "        t.sort()\n",
    "        r = 0\n",
    "        for i, (a, b) in enumerate(t):\n",
    "            r = max(r, b)\n",
    "            if i == r:\n",
    "                return r + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def partdisjoin(nums):\n",
    "    heap = list(nums)\n",
    "    heapify(heap)\n",
    "    left_max=-1\n",
    "    i=0\n",
    "    while i < (len(nums)):\n",
    "        left_max = max(left_max, nums[i])\n",
    "        tmp=left_max\n",
    "        for j in range(i+1,len(nums)):\n",
    "            tmp=max(tmp, nums[j])\n",
    "            if nums[j] < left_max:\n",
    "                left_max=tmp\n",
    "                i = j-1\n",
    "                break\n",
    "        else:\n",
    "            return i+1\n",
    "        i+=1\n",
    "    # no return, inputs are garranted\n",
    "\n",
    "class ST:\n",
    "    def __init__(self, elems: List[int], op: Callable[[int, int], bool], e: Callable[[], int]) -> None:\n",
    "        self.op = op\n",
    "        self.e = e\n",
    "\n",
    "        def log2ceil(n):\n",
    "            r = 1\n",
    "            while r <= n:\n",
    "                r <<= 1\n",
    "            return r\n",
    "        self.sz = log2ceil(len(elems))\n",
    "        self.d = [e() for _ in range(2*self.sz)]\n",
    "        for i, x in enumerate(elems):\n",
    "            self.d[i+self.sz] = x\n",
    "        for i in range(self.sz-1, 0, -1):\n",
    "            self.update(i)\n",
    "\n",
    "    def update(self, i):\n",
    "        op = self.op\n",
    "\n",
    "        self.d[i] = op(self.d[i*2], self.d[i*2+1])\n",
    "\n",
    "    def prod(self, l, r):\n",
    "        op = self.op\n",
    "        lmv, rmv = self.e(), self.e()\n",
    "        l += self.sz\n",
    "        r += self.sz\n",
    "        while l < r:\n",
    "            if l & 1:\n",
    "                lmv = op(lmv, self.d[l])\n",
    "                l += 1\n",
    "            if r & 1:\n",
    "                r -= 1\n",
    "                rmv = op(self.d[r], rmv)\n",
    "            l //= 2\n",
    "            r //= 2\n",
    "        return op(lmv, rmv)\n",
    "\n",
    "\n",
    "def partdisjoin2(nums):\n",
    "    minval_st = ST(nums, min, lambda: float(\"inf\"))\n",
    "    maxval_st = ST(nums, max, lambda: -1)\n",
    "    for i in range(1,len(nums)):\n",
    "        if maxval_st.prod(0, i) <= minval_st.prod(i, len(nums)):\n",
    "            return i\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        return partdisjoin2(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: list) -> int:\n",
    "        n = len(nums)\n",
    "        nums_sorted_idx = [(nums[ii], ii) for ii in range(n)]\n",
    "        nums_sorted_idx = sorted(nums_sorted_idx, key = lambda x: x[0])\n",
    "        max_count = -1\n",
    "        for ii in range(n):\n",
    "            max_count = max(max_count, nums_sorted_idx[ii][1])\n",
    "            if ii == max_count:\n",
    "                return max_count+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: list) -> int:\n",
    "        n = len(nums)\n",
    "        nums_sorted_idx = [(nums[ii], ii) for ii in range(n)]\n",
    "        nums_sorted_idx = sorted(nums_sorted_idx, key = lambda x: x[0])\n",
    "        max_count = -1\n",
    "        for ii in range(n):\n",
    "            max_count = max(max_count, nums_sorted_idx[ii][1])\n",
    "            if ii == max_count:\n",
    "                return max_count+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: list) -> int:\n",
    "        n = len(nums)\n",
    "        nums_sorted_idx = [(nums[ii], ii) for ii in range(n)]\n",
    "        nums_sorted_idx = sorted(nums_sorted_idx, key = lambda x: x[0])\n",
    "        max_count = -1\n",
    "        for ii in range(n):\n",
    "            max_count = max(max_count, nums_sorted_idx[ii][1])\n",
    "            if ii == max_count:\n",
    "                return max_count+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        right_cnt = Counter(nums)\n",
    "        right_cnt = {k:v for k, v in sorted(right_cnt.items(), key=lambda x: x[0])}\n",
    "        left_cnt = defaultdict(int)\n",
    "        left_max = -1\n",
    "        for i in range(len(nums)):\n",
    "            left_cnt[nums[i]] += 1\n",
    "            right_cnt[nums[i]] -= 1\n",
    "            if right_cnt[nums[i]] == 0:\n",
    "                del right_cnt[nums[i]]\n",
    "            left_max = max(left_max, nums[i])\n",
    "            if left_max <= next(iter(right_cnt.items()))[0]:\n",
    "                break\n",
    "        return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        cnt=collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            cnt[nums[i]]+=1\n",
    "        cnt=dict(sorted(cnt.items()))\n",
    "        # print(cnt)\n",
    "\n",
    "        left_max=nums[0]\n",
    "        right_min=min(nums)\n",
    "        left_len=0\n",
    "        for i in range(n):\n",
    "            a=nums[i]\n",
    "            # b=nums[i+1]\n",
    "            left_len+=1\n",
    "            left_max=a if a>left_max else left_max\n",
    "            cnt[a]-=1\n",
    "            if cnt[a]==0: \n",
    "                del cnt[a]\n",
    "            if a==right_min:\n",
    "                right_min=list(cnt.keys())[0]\n",
    "            # print(left_len,left_max,right_min)\n",
    "            # print(cnt)\n",
    "            if left_max<=right_min:\n",
    "                break\n",
    "\n",
    "        return left_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        l = []\n",
    "        cp = 0\n",
    "        for i,n in enumerate(nums):\n",
    "            #print(i,n)\n",
    "            heapq.heappush(l, [n,i])\n",
    "        n,p = heapq.heappop(l)\n",
    "        if p==0:\n",
    "            return 1\n",
    "        else:\n",
    "            mx = p     \n",
    "            cp =0\n",
    "            #print(mx)\n",
    "            while mx>cp:\n",
    "                cp+=1\n",
    "                n,p = heapq.heappop(l) \n",
    "                mx = max(mx,p)  \n",
    "                #print(mx)\n",
    "            return mx+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        nums_with_idx = [[nums[i], i]for i in range(len(nums))]\n",
    "        nums_with_idx.sort()\n",
    "        longest_idx = 0\n",
    "        for i in range(len(nums_with_idx)):\n",
    "            longest_idx = max(longest_idx, nums_with_idx[i][1])\n",
    "            if longest_idx <= i:\n",
    "                return longest_idx + 1\n",
    "        return longest_idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        heap = []\n",
    "        left = nums[0]\n",
    "        for i, n in enumerate(nums):\n",
    "            heapq.heappush(heap, [n, i])\n",
    "        \n",
    "        res = 1\n",
    "        i = 0\n",
    "        while heap and heap[0][0] < left:\n",
    "\n",
    "            res = max(res, heapq.heappop(heap)[1] + 1)\n",
    "            while i < res:\n",
    "                left = max(left, nums[i])\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        max_num = 0\n",
    "        min_num = 10**6\n",
    "\n",
    "        dict_lmax = {}\n",
    "        for i in range(n):\n",
    "            if nums[i] >= max_num:\n",
    "                max_num = nums[i]\n",
    "            dict_lmax[i] = max_num\n",
    "\n",
    "        flag = n - 1\n",
    "        for i in range(n-1,0,-1):\n",
    "            if nums[i] <= min_num:\n",
    "                min_num = nums[i]\n",
    "            if min_num >= dict_lmax[i-1]:\n",
    "                flag = i\n",
    "\n",
    "        return flag\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = {}\n",
    "        d[n - 1] = nums[n - 1]\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            d[i] = min(nums[i], d[i + 1])\n",
    "        max_val = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if d[i] >= max_val:\n",
    "                return i\n",
    "            max_val = max(nums[i], max_val)\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        a=[[nums[i],i] for i in range(len(nums))]\n",
    "        a=sorted(a,key = lambda x:x[0])\n",
    "        ans=0\n",
    "        for i in range(len(a)):\n",
    "            ans=max(ans,a[i][1])\n",
    "            if ans==i:\n",
    "                return i+1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        idx = list(sorted(zip(nums, [i for i in range(n)])))\n",
    "        print(idx)\n",
    "        ans = 0\n",
    "        pre_max = 0\n",
    "        for i in range(n):\n",
    "            pre_max = max(pre_max,idx[i][1])\n",
    "            if pre_max == i:\n",
    "                ans = i\n",
    "                break\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n: int):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "\n",
    "    @staticmethod\n",
    "    def lowbit(x: int) -> int:\n",
    "        return x & (-x)\n",
    "\n",
    "    def update(self, x: int, v: int = 1):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += v\n",
    "            x += BIT.lowbit(x)\n",
    "\n",
    "    def query(self, x: int) -> int:\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tree[x]\n",
    "            x -= BIT.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "    def queryRange(self, x: int, y: int) -> int:\n",
    "        return self.query(y) - self.query(x - 1)\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n, m = 0, len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            nums[i] += 1\n",
    "            n = max(n, nums[i])\n",
    "        \n",
    "        b = BIT(n)\n",
    "        for x in nums:\n",
    "            b.update(x)\n",
    "        \n",
    "        mx = -1\n",
    "        for i, x in enumerate(nums, 1):\n",
    "            mx = max(mx, x)\n",
    "            b.update(x, -1)\n",
    "            if b.queryRange(mx, n) == m - i:\n",
    "                return i\n",
    "        \n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, A: List[int]) -> int:\n",
    "        idx =np.argmin(A)\n",
    "        print(idx)\n",
    "        #left = []\n",
    "        left = [A[i] for i in range(idx+1)]\n",
    "        l_max = max(A[:idx+1])\n",
    "        count = idx + 1\n",
    "        right = idx + 1\n",
    "        r_min = min(A[right:])\n",
    "        if right == len(A):\n",
    "            return right\n",
    "        while l_max > r_min:\n",
    "            element = A[right]\n",
    "            right += 1\n",
    "            count += 1\n",
    "            if element > l_max:\n",
    "                l_max = element\n",
    "            r_min = min(A[right:])\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, A: List[int]) -> int:\n",
    "        idx =np.argmin(A)\n",
    "        print(idx)\n",
    "        left = []\n",
    "        left = [A[i] for i in range(idx+1)]\n",
    "        l_max = max(left)\n",
    "        count = len(left)\n",
    "        right = [A[i] for i in range(idx+1,len(A))]\n",
    "        if right == []:\n",
    "            return len(A)\n",
    "        while l_max > min(right):\n",
    "            element = right.pop(0)\n",
    "            count += 1\n",
    "            if element > l_max:\n",
    "                l_max = element\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, A: List[int]) -> int:\n",
    "        # idx =np.argmin(A)\n",
    "        # print(idx)\n",
    "        # #left = []\n",
    "        # left = [A[i] for i in range(idx+1)]\n",
    "        # l_max = max(A[:idx+1])\n",
    "        # count = idx + 1\n",
    "        # right = idx + 1\n",
    "        # r_min = min(A[right:])\n",
    "        # if right == len(A):\n",
    "        #     return right\n",
    "        # while l_max > r_min:\n",
    "        #     element = A[right]\n",
    "        #     right += 1\n",
    "        #     count += 1\n",
    "        #     if element > l_max:\n",
    "        #         l_max = element\n",
    "        #     r_min = min(A[right:])\n",
    "        # return count\n",
    "\n",
    "\n",
    "        n = len(A)\n",
    "        l_max = [0] * n\n",
    "        r_min = [0] * n\n",
    "        l = A[0]\n",
    "        for i in range(0, n):\n",
    "            l = max(l, A[i])\n",
    "            l_max[i] = l\n",
    "        \n",
    "        r = A[-1]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            r = min(r, A[i])\n",
    "            r_min[i] = r\n",
    "        \n",
    "        for i in range(n-1):\n",
    "            if l_max[i] <= r_min[i+1]:\n",
    "                return i+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        q = [[nums[i], i] for i in range(len(nums))]\n",
    "        heapq.heapify(q)\n",
    "        mi = nums[0]\n",
    "        for i in range(len(nums)-1):\n",
    "            while q[0][1]<=i:\n",
    "                heapq.heappop(q)\n",
    "            if mi<=q[0][0]:\n",
    "                return i+1\n",
    "            mi = max(mi, nums[i+1])\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        max = nums[0] \n",
    "        max_min_list = [[max]]\n",
    "        for n in nums[1:]:\n",
    "            if n > max:\n",
    "                max = n\n",
    "            max_min_list.append([max])\n",
    "        ln = len(nums)\n",
    "        min = nums[ln-1]\n",
    "        max_min_list[ln-2].append(min)\n",
    "        for i in range(2, ln):\n",
    "            if nums[ln-i] < min:\n",
    "                min = nums[ln-i]\n",
    "            max_min_list[ln-i-1].append(min)\n",
    "        for i, (max, min) in enumerate(max_min_list):\n",
    "            if max <= min:\n",
    "                return i +1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p = list(enumerate(nums))\n",
    "        p.sort(key=lambda x : x[1])\n",
    "        print(p)\n",
    "        idx = p[0][0]\n",
    "        max_num = max(nums[:idx + 1])\n",
    "        temp = n + 1\n",
    "        for i in range(p[0][0] + 1, n):\n",
    "            if nums[i] < max_num:\n",
    "                idx = i\n",
    "                if temp < i:\n",
    "                    max_num = nums[temp]\n",
    "            else:\n",
    "                temp = i\n",
    "        return idx + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partitionDisjoint(self, nums: List[int]) -> int:\n",
    "        max_min = [[-math.inf, math.inf] for _ in range(len(nums))]\n",
    "        _max = -math.inf\n",
    "        _min = math.inf\n",
    "        for i in range(len(nums)):\n",
    "            _max = max(nums[i], _max)\n",
    "            max_min[i][0] = _max\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            _min = min(nums[i], _min)\n",
    "            max_min[i][1] = _min\n",
    "\n",
    "        for i in range(len(nums) - 1):\n",
    "            if max_min[i][0] <= max_min[i + 1][1]:\n",
    "                return i + 1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
